import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

public class QueueExercise {
    public static void main(String[] args) {
        int[] arr ={2,6,4,7,3,57,3};
        int[] arr1 = highMinCount(arr,3);
        System.out.println(Arrays.toString(arr1));

    }
    //找出数组中两个最小的数
    //时间复杂度(k+N)logN
    public static int[] minCount(int[] arr) {
        //KlogN;
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();
        for(int i = 0 ; i < arr.length ; i++) {
            priorityQueue.offer(arr[i]);
        }
        int[] arr1 = new int[2];
        //NlogN
        for(int i = 0; i < 2;i++) {
             arr1[i] = priorityQueue.poll();
        }
        return arr1;
    }
    //算法优化：要找几个最小值，那我们要建立一个k个值大根堆，遍历数组，如果大于堆根那么就插入；
    //时间复杂度：K+(N-K)logK;k很小，所以时间复杂度会远小于第一种
    //方法名topk;同时堆顶就是第K个最小的；重点搞清时间复杂度
    public static int[] highMinCount(int[] arr ,int k) {
        int[] arr1 = new int[k];
        if(k == 0){
            return arr1;
        }
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();
        //O(K)
        for(int i = 0; i < k; i++) {
            priorityQueue.offer(arr[i]);
        }
        //O((N - K)logK)
        for(int i = k;i < arr.length;i++) {
            if(arr[i] > priorityQueue.peek()) {
                i++;
            }else {
                priorityQueue.poll();
                priorityQueue.offer(arr[i]);
            }
        }

        int j = 0;
        while(!priorityQueue.isEmpty()){
            arr1[j] = priorityQueue.poll();
            j++;
        }
        return arr1;
    }


}
class imp1 implements Comparator<Integer> {


    @Override
    public int compare(Integer o1, Integer o2) {
        return o2.compareTo(o1);
    }
}
